class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        typedef unsigned long long ULL;
        if (root == nullptr) return 0;
        unordered_map<TreeNode*, ULL> hash;
        hash[root] = 1;
        ULL res = 1;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            int len = q.size();
            ULL mini, maxi;
            for (int i = 0; i < len; i ++ ) {
                auto t = q.front(); q.pop();
                ULL idx = hash[t];
                if (i == 0) mini = idx;
                if (i == len - 1) maxi = idx;
                if (t->left) {
                    q.push(t->left);
                    hash[t->left] = idx * 2;
                }
                if (t->right) {
                    q.push(t->right);
                    hash[t->right] = idx * 2 + 1;
                }
            }
            res = max(res, maxi - mini + 1);
        }
        return res;
    }
};